package 地图软件的最短路径算法;

import java.util.LinkedList;

public class A星算法 {



    private class Graph{

        private int v;

        Vertex[] vertices ;

        private LinkedList<Edge>[] adj;

        public Graph(int v) {
            this.v = v;
            adj = new LinkedList[v];
            for (int i = 0; i < v; i++) {
                adj[i] = new LinkedList<Edge>();
            }
            vertices = new Vertex[this.v];
        }

        private class Vertex{
            public int id;

            public int dist;

            public int f;

            public int x;

            public int y;

            public Vertex(int id, int x, int y) {
                this.id = id;
                this.f = Integer.MAX_VALUE;
                this.dist = Integer.MAX_VALUE;
                this.x = x;
                this.y = y;
            }
        }

        public void addVertex(int id, int x, int y){
            vertices[id] = new Vertex(id,x , y);
        }

        public void addEdge(int start,int end,int weight){
            adj[start].add(new Edge(start, end, weight));
            //这是一个无向图
            adj[end].add(new Edge(end, start, weight));

        }

        private class Edge{//图中的边

            /**
             * 起始点编号
             */
            private int start;

            /**
             * 结束点编号
             */
            private int end;

            /**
             * 权重
             */
            private int weight;

            public Edge(int start, int end, int weight) {
                this.start = start;
                this.end = end;
                this.weight = weight;
            }
        }

        //自己实现一个优先级队列(一个小顶堆)
        private class PriorityQueue{

            //小顶堆的一维数组表现形式
            private Vertex[] nodes;

            //堆的大小
            private int n;

            //当前堆有多少数据
            private int count;

            public PriorityQueue(int n) {
                //方便计算,多申请一个空间
                nodes = new Vertex[n+1];
                this.n = n;
                count = 0;
            }

            //模拟出队操作
            public Vertex poll(){
                if (isEmpty()){
                    System.out.println("队空");
                    throw new NullPointerException();
                }
                Vertex result = nodes[1];
                //重新堆化
                Vertex node = nodes[count];
                nodes[count] = null;
                count--;
                nodes[1] = node;
                int cur = 1;
                while (true){
                    int minPos = cur;
                    if (2*cur <= count && node.f > nodes[2*cur].f){
                        minPos = 2*cur;
                    }
                    if (2*cur+1 <= count && nodes[minPos].f > nodes[2*cur+1].f){
                        minPos = 2*cur+1;
                    }
                    if (minPos == cur){
                        break;
                    }
                    swap(cur,minPos );
                    cur = minPos;
                }
                return result;
            }

            public void update(Vertex vertex){
                for (int i = 1; i <= count; i++) {
                    if (nodes[i].id == vertex.id){
                        nodes[i].f = vertex.f;
                        int cur = i;
                        while (cur>=2){
                            if (vertex.f < nodes[cur/2].f){
                                swap(cur,cur/2 );
                                cur /= 2;
                            }else {
                                nodes[cur] = vertex;
                                break;
                            }
                        }
                        break;
                    }
                }

            }

            //模拟入队操作
            public void add(Vertex vertex){
                if (isFull()){
                    System.out.println("队满");
                    throw new RuntimeException("队满");
                }
                if (isEmpty()){
                    nodes[1] = vertex;
                    count++;
                    return;
                }
                count++;
                int cur = count;
                nodes[cur] = vertex;
                while (cur>=2){
                    if (vertex.f < nodes[cur/2].f){
                        swap(cur,cur/2 );
                        cur /= 2;
                    }else {
                        nodes[cur] = vertex;
                        break;
                    }
                }

            }

            public boolean isEmpty(){
                return count == 0;
            }

            public boolean isFull(){
                return count == n;
            }

            public void swap(int n,int m){
                Vertex temp = nodes[n];
                nodes[n] = nodes[m];
                nodes[m] = temp;
            }

            public void clear(){
                for (int i = 1; i < count; i++) {
                    nodes[i] = null;
                }
                count = 0;

            }

        }
        public void astar(int s, int t) {
            int[] predecessor = new int[v];
            boolean[] inQueue = new boolean[v];
            PriorityQueue queue = new PriorityQueue(v);
            Vertex start = vertices[s];
            Vertex end = vertices[t];
            start.dist = 0;
            start.f = 0;
            queue.add(start);
            inQueue[s] = true;
            while (!queue.isEmpty()){
                Vertex cur = queue.poll();
                int curId = cur.id;
                for (Edge edge : adj[curId]) {
                    int nextId = edge.end;
                    Vertex next = vertices[nextId];
                    if (vertices[curId].dist + edge.weight < next.dist){
                        next.dist = vertices[curId].dist + edge.weight;
                        next.f = Math.abs(end.x - next.x)+Math.abs(end.y - next.y) + next.dist;
                        predecessor[nextId] = curId;
                        if (inQueue[nextId]){
                            queue.update(next);
                        }else {
                            inQueue[nextId] = true;
                            queue.add(next);
                        }
                    }
                    if (nextId == t){
                        queue.clear();
                        break;
                    }
                }

            }
            System.out.print(s);
            print(s,t , predecessor);
        }

        private void print(int s, int t, int[] predecessor) {
            if (s==t){
                return;
            }
            print(s,predecessor[t] ,predecessor );
            System.out.print("->" + t);
        }
    }

    public static void main(String[] args) {
        //A星算法 a星算法 = new A星算法();
        //a星算法.test();
        Integer a = 100, b = 100,c = 150,d= 150;
        System.out.println(a==b);
        System.out.println(c==d);
    }

    public void test(){
        Graph graph = new Graph(14);
        graph.addEdge(0,1 , 20);
        graph.addEdge(0,4 , 60);
        graph.addEdge(0,5 , 60);
        graph.addEdge(0,6 , 60);
        graph.addEdge(1,2 , 20);
        graph.addEdge(2,3 , 10);
        graph.addEdge(3,12 , 40);
        graph.addEdge(3,13 , 30);
        graph.addEdge(4,8 , 50);
        graph.addEdge(4,12 , 40);
        graph.addEdge(5,8 , 70);
        graph.addEdge(5,9 , 80);
        graph.addEdge(5,10 , 50);
        graph.addEdge(6,7 , 70);
        graph.addEdge(6,13 , 50);
        graph.addEdge(7,11 , 50);
        graph.addEdge(8,9 , 50);
        graph.addEdge(9,10 , 60);
        graph.addEdge(10,11 , 60);
        graph.addVertex(0, 320, 630);
        graph.addVertex(1, 300, 630);
        graph.addVertex(2, 280, 625);
        graph.addVertex(3, 270, 630);
        graph.addVertex(4, 320 , 700);
        graph.addVertex(5, 360, 620);
        graph.addVertex(6, 320, 590);
        graph.addVertex(7, 370, 580);
        graph.addVertex(8, 350, 730);
        graph.addVertex(9, 390, 690);
        graph.addVertex(10, 400, 620);
        graph.astar(0,10 );

    }
}


